# 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
# 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
# 你可以认为每种硬币的数量是无限的。

from typing import List


class Solution:

    def coinChange(self, coins: List[int], amount: int) -> int:
        """动态规划"""
        dp = [0] * (amount + 1)
        # amount为0，表示不需要硬币，也算一个组合
        dp[0] = 1
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] += dp[x - coin]
        return dp[-1]


if __name__ == "__main__":
    print(Solution().coinChange(coins=[1, 2, 3], amount=6))
    # print(Solution().coinChange(coins=[2], amount=3))
    # print(Solution().coinChange(coins=[1], amount=0))
    # print(Solution().coinChange(coins=[1], amount=1))
    print(Solution().coinChange(coins=[186, 419, 83, 408], amount=6249))
